'''
1. 使用递归将源数列使用二分法分成多个子列
从中间分开！
2. 申请空间将两个子列排序合并然后返回

3. 将所有子列一步一步合并最后完成排序
注：先分解再归并
'''
def mergeSort(arr):
    if len(arr) ==1:
        return arr
    # 分治就是先分再治，左右分，粒度到1为止！
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]
    return merge(mergeSort(left),mergeSort(right))

def divide(arr):
    # 分治就是先分再治，左右分，粒度到1为止！
    if len(arr) == 1: return arr
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]
    return merge(divide(left),divide(right))
# 治就是把小的放在左边，大的放在右边！
def merge(left,right):
    res =[]
    while right and left:
        # 从左到右的比
        if right[0] < left[0]:
            res.append(right.pop(0))
        else:
            res.append(left.pop(0))
    res += left
    res += right
    return res



def merge(left,right):
    # 不能用or因为涉及到索引，not right的话index会报错！
    # 为甚么0 可以 -1就不可以？ 从前面开始！后面合并起来也是从前面开始
    # 因为归并的时候是从前到后的做，如果-1的话需要从后向前，res的顺序就不对了，需要返回res[::-1]
    res = []
    while right and left:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res += left
    res += right

    return res
ilist = mergeSort([4, 5, 6, 7, 3, 2, 6, 9, 8,10])
print(ilist)

def merge(left,right):
    res = []
    # 不能用or因为涉及到索引，not right的话index会报错！
    # 为甚么0 可以 -1就不可以？ 从前面开始！后面合并起来也是从前面开始
    # 因为归并的时候是从前到后的做，如果-1的话需要从后向前，res的顺序就不对了，需要返回res[::-1]
    while left and right:
        if left[-1] <= right[-1]:
            res.append(right.pop())
        else:
            res.append(left.pop())
    res += left[::-1]
    res += right[::-1]
    # print('res=',res)
    return res[::-1]
# [2, 6, 3, 4, 5, 6, 7, 8, 9, 10]
ilist = mergeSort([4, 5, 6, 7, 3, 2, 6, 9, 8,10])
print(ilist)
